package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
https://leetcode.cn/problems/find-bottom-left-tree-value/description/

513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

示例 1:
输入: root = [2,1,3]
输出: 1

示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
 */
class leetcode_513 {
    @Test
    fun test_1() {
        val root = TreeNode(2)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        root.left = n1
        root.right = n3
        val actual = findBottomLeftValue(root)
        val expect = 1
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        root.left = n2
        root.right = n3
        n2.left = n4
        n3.left = n5
        n3.right = n6
        n5.left = n7

        val actual = findBottomLeftValue(root)
        val expect = 7
        Assert.assertEquals(expect, actual)
    }

    private fun findBottomLeftValue(root: TreeNode?): Int {
        // 深度最大，第一个孩子：当深度变大时，这个节点就是当前深度的最左孩子
        // 如果最大一层，只有一个右孩子，它也是最左边的节点
        // findBottomLeftValue1(root,1)
        // return num
        return findBottomLeftValue2(root)
    }

    var num: Int = Int.MIN_VALUE
    var maxDepth: Int = 0
    private fun findBottomLeftValue1(root: TreeNode?, currentDepth: Int) {
        // 深度遍历 - 前序 中左右 - 递归
        // T - N
        // S - 1
        if (null == root) {
            return
        }
        // 结束条件
        if (root.left == null && root.right == null && currentDepth > maxDepth) {
            maxDepth = currentDepth
            num = root.`val`
        }

        var depth = currentDepth
        // 左
        root.left?.let {
            depth++
            findBottomLeftValue1(it, depth)
            depth-- // 回溯过程
        }

        // 右
        root.right?.let {
            depth++
            findBottomLeftValue1(it, depth)
            depth-- // 回溯过程
        }

        // 中
        // 没有这里处理步骤
    }

    private fun findBottomLeftValue2(root: TreeNode?): Int {
        // 层级遍历 - 迭代，每层的第一个孩子就是最左孩子
        // T - N
        // S - N
        if (root == null) {
            return 0
        }

        var num: Int = Int.MIN_VALUE
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)

        while (!queue.isEmpty()) {
            val size: Int = queue.size
            for (i in 1..size) {
                val node: TreeNode = queue.poll()
                if (i == 1) {
                    num = node.`val`
                }
                node.left?.let {
                    queue.offer(it)
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
        }
        return num
    }
}